\|\\M0basl30;\M2germ35;\M9fix20;\←=90;\ε\`'10004;\F0\;

1.	Introduction

\J	Since its beginnings over 2000 years ago,  cryptography  has  progressed
from  a simple adjunct to writing into an elaborate and highly mathematical art.
Advances in computing machinery and accompanying developments in the  theory  of
computation  have brought us today to the brink of a revolution in cryptography.
On the one hand, the decreasing cost  of  computation  has  brought  high  grade
cryptography  into a price range where its addition would not greatly affect the
cost of a computer terminal.  And, on the other hand,  theoretical  advances  in
computer science, most notably in computational complexity, promise to allow the
development of provably secure systems thereby changing the art to a science. In
addition  the  development  of  large  computer  and  communication networks has
compounded the key distribution problem which was already present  in  classical
cryptgraphy.   We  propose that it is possible to eliminate this problem through
use of public key cryptosystems in which all key distribution can be  cone  over
isecure  channels.   These developments are still in an embroyonic stage and are
presented as open research problems.
	While  the  new  systems suggested in this paper are radically different
from conventional systems, in retrospect,  our  suggested  developments  can  be
viewed  as  the  natural  culmination  of  trends  which  have  been  visible in
cryptography during the last several centuries.
	As  an example of one such trend, early cryptosystems such as the Caesar
cipher (in which each letter is replaced by the one three places further on,  so
A  is  carried  to  D,  B  to  E, etc.) required that the general system be kept
secret.  During the Renaissance the distinction between a general system  and  a
specific  key  allowed  the  general system to be compromised, for example as by
theft of a cryptographic device, without compromising future messages enciphered
in  new  keys.  Then, about 1960, cryptosystems were developed which were deemed
strong  enough  to  resist  a  cryptanalytic  attack  even  when  the  plaintext
(unenciphered)  messages  corresponding  to  previous  cryptograms  were  known,
thereby eliminating the burdon of keeping old messages secret.   Each  of  these
developments  decreased the portion of the system which had to be protected from
public knowledge, and allowed more transparent use of the system.
	Today,  one  of  the  major  barriers  to  use  of cryptography in large
computer or communication networks is the secrecy of the key and  the  resulting
key distribution problem.  Two users who wish to establish contact for the first
time must either use an external, secure channel  such  as  registered  mail  to
exchange  keys;  or,  if each user has a distinct key for communicating with the
network and if the network can be trusted, they can  communicate  securely  with
the  network,  and  therefore  with  each  other.[,,,]  However, it appears that
securing the network is a formidable task.
	We  suggest  that  as  the  culmination  of this trend toward decreasing
secrecy it may be  possible  to  eliminate  the  secrecy  of  the  key  used  in
encryption,  and  yet  to  preserve  the  privacy  of the communication. This is
accomplished by each user having a pair of keys E and D.    E is an  enciphering
key and is public information. D is the corresponding deciphering key, and while
kept secret, need never be communicated, thereby  eliminating  the  need  for  a
secure  key  distribution channel.  While D is, in principle, computable from E,
the cost of this  computation  is  infeasibly  high.   We  shall  use  the  term
_computationally  infeasible_  to  refer  to  tasks which requrire an impossibly
large number (e.g., 10↑100) of operations.    Thus,  the  terms  computationally
infeasible and uncomputable are, in practice, synonymous.

	Later  sections  explore  public key cryptosystems in greater detail and
give arguments which support their existence.


	A related problem treated in this paper is that of authentication.  Here
we  suggest  that  oneway  IFF authentication systems may exist.  These combine
desirable features of oneway login procedures (described later in this section)
and  desirable  features  of  IFF  systems (described in section 2).   These two
authentication procedures protect against different threats.     An  IFF  system
prevents  an  eavesdropper  from  using  a  previously  overheard authentication
exchange to falsely pose as a legitimate user of the system.    IFF  systems  do
not,  however,  prevent  the system (or someone who has stolen system data) from
forging  a  login,  since  both  the  user  and  the  system  possess  identical
authentication  keys.    oneway  login procedures have a different goal.   They
prevent knowledge of the system's  authetication  keys  from  being  misused  to
impersonate a user.
	A oneway IFF system would protect against both of these  threats.   The
system would issue a time dependent challenge, so no challenge is ever repeated.
The user responds to the challenge with a response which is a function  of  both
the   challenge   and  a  secret  authentication  key.    The  system  possesses
information related to the secret key which allows it to verify the authenticity
of  the  response.    But it is computationally infeasible for the system to use
this information to calculate the correct response to its own  challenge.   Thus
an  eavesdropper  cannot use a previously overheard response because it was only
valid at the time it was issued, and even if he were to steal the authentication
tables  used  by  the  system  he  could not use this data to calculate a proper
response.
	Both public key cryptosystems and oneway IFF systems may at first glace
appear to be logical impossibilities. In an effort to  offset  this  feeling  we
will  now pose another problem with somewhat the same flavor, but which has been
successfully solved in practice.
	Consider the login problem in a multiuser computer system.  When setting
up his account the user chooses on a password which is entered into the system's
password  directory.   Each  time he logs in, the user is asked to again provide
his password.  By keeping this password  secret  from  all  other  users  forged
logins are prevented.  This, however, makes it vital to preserve the security of
the password directory since the information it  contains  would  allow  perfect
impersonation  of  any  user.       The  problem is further compounded if system
operators have legitimate reasons for accessing the directory.    Allowing  such
legitimate accesses, but preventing all others is next to impossible
	This leads to the apperently impossible  requirement  for  a  new  login
procedure  capable  of  judging  the  authenticity of passwords without actually
knowing them.     While again appearing to  be  a  logical  impossibility,  this
proposal  is easily satisfied.  When the user first enters his passowrd, PW, the
computer automatically and transparently computes a function  f(PW)  and  stores
this,  not  PW,  in  the  password  directory.     At each successive login, the
computer calculates f(X), where X is the proferred password, and  compares  f(X)
with  f(PW).   If  and  only  if  they  are equal, the user is accepted as being
authentic. Since  the  function  f  must  be  calculated  once  per  login,  its
computation  time  must  be  small.  A million instructions (with an approximate
cost of $0.10) seems to be a reasonable limit on this computation.  If we  could
ensure,   however,  that  calculation  of  f\∩-1\⊗  required  10\∩30\⊗  or  more
instructions, someone who had  subverted  the  system  to  obtain  the  password
directory could not in practice obtain PW from f(PW), and could thus not perform
an unauthorized login.
	Note  that  we  assume  that the function f(.) is public information, so
that it  is  not  ignorance  of  f(.)  which  makes  calculation  of  f\∩-1\⊗(.)
difficult.


	Functions  with  this  property  were  first  suggested for use in login
procedures by R. M. Needham [] and are discussed in two recent papers [,].    Up
to  now  they  have  been called oneway ciphers, but we prefer the term oneway
function  to  avoid  confusion  with  other  entities   such   as   public   key
cryptosystems.    With  this  terminology,  a  function f is oneway if, for any
argument x in the domain it is easy to compute the corresponding value y = f(x),
yet  for almost all y in the range it is computationally infeasible to solve the
equation y = f(x) for a suitable argument x.    It is  very  important  to  note
that  we  are  defining  a function which is not invertible from a computational
point of view, but whose  non-invertibility  is  entirely  different  from  that
normally   encountered  in  mathematics.    A  function  f  is  normally  called
"non-invertible" when the inverse of a point y = f(x) is not unique, (ie.  there
exist distinct points x1 & x2 such that f(x1) = f(x2) ).  We emphasize that this
is not the sort of inversion difficulty which we require. Rather, we insist that
it  must  be  overwhelmingly  difficult  given  a  value y and knowledge of f to
calculate any x whatsoever with the property that f(x) = y
	Indeed,  if f is non-invertible in the usual sense, it may make the task
of finding an inverse image easier.  In the extreme, if f(x) ≡ y\∪0\⊗ for all  x
in  the  domain  then  the  range  of  f  is  {y\∪0\⊗}, and we can take any x as
f↑-1(y0).   It is therefore desirable that f not be  too  degenerate.   A  small
degree  of  degeneracy is tolerable and, as discussed later, is probably present
in the most promising class of oneway functions.
	Polynomials  are  an elementary example of oneway functions. It is much
harder to find a root x\∪0\⊗ of the polynomial equation p(x) = y than it  is  to
evaluate  the  polynomial  p(x)  at  x  =  x\∪0\⊗.  oneway  functions and their
theoretical  basis  are  discussed  at  greater  length  in  section  4.   Their
introduction  at  this  point  is intended to diminish skepticism concerning the
newly suggested public key cryptosystems and oneway IFF systems.
	Section 3 defines six general problem areas and a number of subproblems.
The relationships among these problems are also discussed.  Section 4 is devoted
to  a  study of oneway functions and section 5 to a discussion of computational
complexity and its cryptographic applications.
	To  establish  notation,  in section 2, we will first review the flow of
information in conventional cryptographic and IFF systems.